FIG. 1 depicts a communications network 10 called an internet. The internet 10 includes a number of stubs 20, 30, 40, and 50. Each stub 20, 30, 40, and 50 is a smaller, subsumed communications network. The stub 20 comprises the nodes 21,22,23, the stub 30 comprises the nodes 31,32,33,34, the stub 40 comprises the nodes 41,42, and the stub 50 comprises the nodes 51,52. The nodes 21-23, 31-34, 41-42, and 51-52 within each stub 20, 30, 40, and 50 are interconnected by a respective subnetwork 25, 35, 45, or 55 of the stub. For example, the nodes 21-23 are interconnected by the subnetwork 25 of the stub 20. As used herein, the term "subnetwork" refers to the communications lines, switches, etc. necessary for establishing internodal communication amongst the nodes interconnected by that particular subnetwork. For example, the subnetwork 25 can establish communications between any of the nodes 21-23 within the stub 20.
FIG. 2 depicts a node, e.g., the node 32 of the internet 10, in greater detail. As depicted, each node comprises a CPU or processor 71, a memory 72, and one or more input/output ports 73-1, 73-2, . . . , 73-n which are interconnected to one another via a bus 74. The input/output ports 73-1, 73-2, . . . , 73-n may be connected to the input/output ports of another node (e.g., the node 31) via a subnetwork (e.g., the subnetwork 35). The processor 71, among other things, controls the transmission of data between the memory 72 and the input/output ports 73-1, 73-2, . . . , 73-n. The processor 71 also controls the transmission of data from the input/output ports 73-1, 73-2, . . . , 73-n to other nodes. For example, the processor 71 can cause data stored in the memory 72, to be transmitted via the bus 74 to a particular input/output port, e.g., the input/output port 73-2. The processor 71 can then cause the input/output port 73-2 to transmit the data via the subnetwork 35 to a second node, e.g., the node 31. The data may be received in an input/output port at the node 31 and then transferred via the bus at that node 31 into the memory thereat under the control of the processor of the node 31.
It is also possible to transmit data from the node 31 to the node 32 by transmitting the data from the node 31 to the node 33, and then from the node 33 to the node 32. The transmission between each pair of nodes, e.g., from the node 31 to the node 33, is achieved in the above described manner.
The node at which data is initially generated and transmitted (e.g., the node 32) is called the source node. The node to which the data is ultimately destined (e.g., the node 31) is called the destination node. All other nodes between the source and destination node through which the data may pass (e.g., the node 33) are referred to as intermediary nodes.
Illustratively, data transmitted between nodes via a subnetwork within a particular stub is organized into packets. Such a packet 80 is depicted in FIG. 3. The packet contains one or more headers 81, 82 and data 83. One header 81 of the packet 80 is associated with the subnetwork over which the packet is to be transmitted and is called the subnetwork header. This subnetwork header contains control information including information necessary to direct the packet to its destination within that particular stub. Each node connected to the subnetwork is assigned a subnetwork address or identifier which is recognized by every other node connected to the subnetwork. The subnetwork header typically contains the subnetwork address of the source node, called the source address, and the subnetwork address of the destination node, called the destination address.
When a source node transmits a packet to a destination node in the same stub, the source node places its subnetwork address in the subnetwork source address field 81-1 (FIG. 3). Furthermore, the source node places the subnetwork address of the destination node in the subnetwork destination address field 81-2 of the packet 80. Thus, the source node must know or determine the subnetwork address of the destination node. In the case that the stub containing the source and destination nodes is an Ethernet network, the source node may already store the subnetwork address of the destination node in the memory of the source node. If the source node does not already store the destination address, the source node can transmit a query message to all nodes of the stub. The query message identifies the destination node and requests that the destination node transmit its subnetwork address to the source node. Upon receiving the query message, the destination node transmits its subnetwork address to the source node. All other nodes in the stub ignore the query message. Using the subnetwork address of the destination node, the source node then transmits its packet to the destination node.
When a packet is received at a node, the processor at the node illustratively determines if the node has the same subnetwork address as the destination address of the packet. If so, the processor at the node determines that the packet has reached its destination within that particular stub. If the destination address is different from the node's subnetwork address, the processor determines that the packet is not at its destination within that stub. The processor then determines the appropriate manner for transmitting the packet so that the packet reaches its destination node.
Often it is desirable to transmit packets from a source node in one stub to a destination node in another stub in the internet 10 of FIG. 1. To that end, each stub 20, 30, 40 and 50 has one or more access point nodes 21, 31, 34, 41, and 51, respectively, which are interconnected by a separate transit or backbone subnetwork called a public data network or PDN 60. A transit or backbone subnetwork is a subnetwork which may be used for transmitting packets between stubs. Thus, it is possible to transmit a packet from the node 23 in the stub 20 to the node 33 in the stub 30 by first transmitting the packet from the node 23 to the node 21 via the subnetwork 25. The packet is then transmitted from the node 21 to the node 31, via a backbone subnetwork in the form of the PDN 60, and from the node 31 to the node 33 via the subnetwork 35 in the stub 30. An access point node which receives a packet from a stub and retransmits the packet via the PDN 60, e.g., the node 21, is referred to as an entry point node of the PDN 60. An access point node which receives a packet from the PDN 60 and retransmits the packet via the subnetwork of a stub, e.g., the node 31, is referred to as an exit point node of the PDN 60.
In the internet 10, it is assumed that packets may not be transmitted from an access point node in a first stub to an access point node in a second stub via the subnetwork of a third stub. In other words, if a packet is received at an access point node of a third stub from the PDN 60 it may only be retransmitted therefrom via the subnetwork of the third stub to a destination node in that stub. If such a received packet is destined to a node in another stub, it may only be retransmitted from the access point node of the third stub via the PDN 60.
The PDN 60 may be a connection-less or a connection oriented subnetwork. An example of a connection oriented PDN 60 would be a telephone network.
Like the subnetworks 25, 35, 45 and 55, the PDN 60 provides a PDN subnetwork address for each access point node 21, 31, 34, 41, and 51. Typically, the subnetworks 25, 35, 45, 55 and the PDN subnetwork 60 utilize different addressing schemes. Thus, each node 21-23, 31-34, 41-42, and 51-52 of the internet 10 is further assigned an internet address. Furthermore, packets may be transmitted with internet headers containing the internet addresses of the source and destination nodes. Such an internet packet 90 is depicted in FIG. 4 with a subnetwork header 91, an internet header 92 and data 93. The internet header 92 contains the internet address of the source and destination nodes in an internet source address field 92-1, and internet destination address field 92-2, respectively.
Subnetwork addresses are recognizable only by the nodes connected to that particular subnetwork. Internet addresses have significance over the entire internet 10. The internet address of a packet's destination node may be used to determine whether the packet must be transmitted via the PDN 60 in order to reach the destination node. The internet address of a packet's destination node may also be used at a first access point node to direct a received packet to a second access point node via the PDN 60. That is, suppose a first entry point node receives a packet via a first stub but must transmit the packet to a second exit point node in a second stub via the PDN 60. The first access point node may use the internet destination address of the packet to determine the PDN subnetwork address of the second access point node. For example, suppose the node 21 receives, via the subnetwork 25, a packet from the node 23 having the internet destination address for the node 42. When the node 21 receives the packet, the node 21 uses the internet destination address in the internet destination address field 92-2 (FIG. 4) of the packet to determine over which subnetwork to retransmit the packet. In this case, the node 21 determines that the packet must be retransmitted via the PDN 60 to reach the node 41, which is the next node on the path to the node 42. If the node 21 determines that the packet must be retransmitted via the PDN 60, then the node 21 uses the internet destination address of the packet to determine the PDN subnetwork address of the next node on the path to the node 42. In this case, the node 21 determines the PDN subnetwork address of the node 41.
In order for an entry point node, such as the node 21, to make these two determinations, each access point node illustratively stores an internet routing table, such as the internet routing table 85 shown in FIG. 5. FIG. 5 shows an illustrative internet routing table at the node 21, having an entry 85-1, 85-2, 85-3, 85-4, 85-5, 85-6, 85-7, 85-8, 85-9, 85-10, and 85-11 for each node of the internet 10. In the alternative, where there are many nodes on the internet 10, each node stores entries for only some of the nodes or provides individual entries for different subsets of nodes, or both. In FIG. 5, each entry has a first field which stores the internet destination address of a different node. The subscript I is used to designate internet addresses, i e., "31.sub.I " means the internet address of the node 31. Each entry has a second field which stores the PDN subnetwork address of the next node on the path to the destination node having the corresponding internet destination address. In FIG. 5, the subscript PDN is used to designate PDN subnetwork addresses, i e., "31.sub.PDN " means the PDN subnetwork address of the node 31. Furthermore, each entry has a third field which stores an indicator of the subnetwork over which a packet must be retransmitted. The entries 85-9, 85-10, and 85-11 correspond to nodes 21-23 which are connected to the node 21 via the subnetwork 25, not the PDN 60 as indicated by the third field of these entries. The second field of each of these entries is not used for routing the packets (rather, the packets are routed within the stub 20 as discussed above) as indicated by "don't care" in FIG. 5.
Continuing with the above example wherein a packet is transmitted from node 23, to node 21, to node 41, to node 42, the processor at the node 21 searches the table 85 for the entry corresponding to the internet destination address contained in the packet, i.e., the entry 85-6 which stores the internet address of the node 42. The processor of the node 21 examines the third field of this entry 85-6 and determines that the packet must be retransmitted via the PDN 60. The processor at the node 21 then uses the PDN subnetwork address stored in the next node field of the retrieved entry 85-6 to retransmit the packet to the next node on the path to the node 42, i.e., the node 41, via the PDN 60.
In the alternative, the entry point node 21 may not know the PDN subnetwork address of the exit point node 41. In other words, the node 21 does not know the direct optimal path between the entry point node 21 and the exit point node 41. Instead, the entry point node 21 must transmit the packet to the exit point node 41 via a sequence of at least one intermediary access point node. For instance, instead of the PDN subnetwork address of the exit point node 41, the entry 85-6 may store the PDN subnetwork address of the access point node 31 in its next node field. The entry point node 21 would thus transmit the packet to a first intermediary access point node, i.e., to the access point node 31. The access point node 31 then illustratively consults its internet routing table to determine if it knows the PDN subnetwork address of the exit point node 41. If so, the packet is transmitted directly to the exit point node 41. If not, the intermediary access point node 31 may transmit the packet to yet another intermediary access point node in a similar fashion as described above. Thus, the packet is transmitted from intermediary access point node to intermediary access point node in the PDN 60 until it arrives at an intermediary access point node which knows the PDN subnetwork address of the exit point node 41.
The overhead in determining, at the entry point node, the PDN subnetwork address of the exit point node of a packet (i.e., the optimal path across the PDN 60) depends on the size of the internet. In the case of small, broadcast local area networks (LANs), the determination of the LAN subnetwork address of any desired destination node is a simple task. See, D. Plummer, "An Ethernet Address Solution Protocol--or--Converting Network Protocol Addresses to 48 bit Ethernet Addresses for Transmission on Ethernet Hardware," RFC 826 USC Information Sciences Institute, November, 1982. This is because broadcast LANs interconnect a small number (hundreds) of nodes and posses a simple, low overhead mechanism for "searching" for the LAN subnetwork addresses of other nodes. However, on a very large, general topology PDN subnetwork, the task of determining subnetwork destination addresses is more difficult. The Public Data Network (PDN) may be connected to tens of thousands of nodes rendering the task of distributing up-to-date PDN subnetwork addresses about each node to each other node highly inefficient. Thus, in a large PDN, the nodes can only maintain the PDN subnetwork address of a subset of nodes. This means that an entry point node often does not know the PDN subnetwork address of the exit point node and thus cannot transmit a packet directly thereto via the optimal path. Instead, the packet must be transmitted from the entry point node to the exit point node via a sequence of intermediary access point nodes of the PDN as described above. Moreover, although any access point node should be capable of communicating with any other access point node via the PDN, most access point nodes are unlikely to communicate with the majority of the other access point nodes. It is thus unnecessary for each access point node to maintain information about every other access point node.
Several solutions for the above problem been proposed, i.e., for determining, at an entry point node, the PDN subnetwork address of the exit point node. See, International Standards Organization, "End System to Intermediate System Routing Information Exchange Protocol for Use in Conjunction with ISO 8878," ISO 10030. A first solution has been proposed for an internet having stubs which are each connected with a PDN by only one access point node. The internet address assigned to each node contains the PDN subnetwork address of the corresponding access point node. Thus, it is a simple matter to determine, at an entry point node, the PDN subnetwork address of the exit point node which connects the stub containing the destination node. The entry point node simply examines the internet address of the destination node of the packet and extracts the PDN subnetwork address of the exit point node therefrom.
In a second solution, a small number of nodes are designated as "route server nodes". All non-route server nodes of the internet advertise the subnetworks and stubs they can reach to the route server nodes to which they are connected. The route server nodes, in turn, exchange this received information with other route server nodes.
The second solution works as follows. Suppose a non-route server node X is an access point node to the PDN for a source node S which desires to transmit a packet to a destination node D in another stub. In such a case, the source node S transmits a packet to the access point node X via a subnetwork. The node X transmits the packet to the route server node with which it is connected. The route server node determines the PDN subnetwork address of the exit point node Y that connects the stub containing the destination node D with the PDN, for example, by consulting its internet routing table (FIG. 5). The route server node then transmits the packet to this node Y (which in turn transmits the packet to the node D). In addition, the route server node transmits a redirect packet back to the node X which contains the PDN subnetwork address of the node Y. The node X stores the subnetwork address of the node Y for later use in transmitting other packets to the node D. Thus, the node X can now transmit a packet directly to the node Y (i.e., via the optimal path).
Each of these solutions has drawbacks. In the first solution, the internet addresses must be very large. Thus, the solution is not applicable to many widely deployed subnetworks, such as those employing the DECNET, Appletalk or Novell IPX protocols which restrict the size of addresses. Furthermore, it is not possible to embed the PDN subnetwork address of the exit point node in the internet destination address if the PDN has stubs that have more than one access point node each to the PDN. This is significant because it is prudent to connect two nodes of even small stubs with the PDN for purposes of reliability,
The second solution places a heavy load on the route server nodes in terms of handling routing updates, storing routes, forwarding packets and redirecting router nodes. Thus, each route server node is a potential bottleneck.
It is therefore an object of the present invention to provide for routing data in a PDN subnetwork of an internet which overcomes the disadvantages of the prior art.